package cn.jietuo.first.class04;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/7/7
 * @description: 堆排序
 * <pre>
 * 1，先让整个数组都变成大根堆结构，建立堆的过程:
 *     1)从上到下的方法，时间复杂度为O(N*logN)
 *     2)从下到上的方法，时间复杂度为O(N)
 * 2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)
 * 3，堆的大小减小成0之后，排序完成
 * </pre>
 */
public class Code02_HeapSort {

    public void heapSort(int[] arr) {
        if (arr == null || arr.length < 1) {
            return;
        }
//        for (int i = 0; i < arr.length; i++) {
        // O(N*logN)
//            heapInsert(arr, i);
//        }

        for (int i = arr.length - 1; i >= 0; i--) {
            // O(logN)
            heapify(arr, i, arr.length);
        }

        int size = arr.length;
        // 大根堆-》 有序数组
        // 第一个与最后一个数字交换，然后继续heapInsert
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private void heapInsert(int[] arr, int index) {
        int left = index * 2 + 1;
        while (left < arr.length) {
            int largest = left + 1 < arr.length && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private void swap(int[] arr, int index, int largest) {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 3, 7, 23, 56, 23};
        Code02_HeapSort code02_heapSort = new Code02_HeapSort();
        code02_heapSort.heapSort(arr);
        printArr(arr);
    }

    private static void printArr(int[] arr) {
        for (int i : arr) {
            System.out.println(i);
        }
    }

}
